package hw2_TSP;

import ilog.concert.*;
import ilog.cplex.*;
//import java.io.BufferedReader;
//import java.io.File;
//import java.io.FileInputStream;
//import java.io.InputStreamReader;
//import java.util.Arrays;

public class second {
	
//	public static int[] readTxt(String txtPath) {
//        File file = new File(txtPath);
//        if(file.isFile() && file.exists())
//        {
//            try {
//                FileInputStream fileInputStream = new FileInputStream(file);
//                InputStreamReader inputStreamReader = new InputStreamReader(fileInputStream);
//                BufferedReader bufferedReader = new BufferedReader(inputStreamReader);              
//                int[] re = new int[225];
//                String text = null;
//                int i=0;
//                while((text = bufferedReader.readLine()) != null){
//                	if(Character.isDigit(text.charAt(0))) {
//                		re[i] = Integer.parseInt(text);
//                		i++;
//                	}
//                }
//                bufferedReader.close();
//                Arrays.sort(re);
//                return re;
//            } catch (Exception e) {
//                e.printStackTrace();
//            }
//        }
//        return null;
//    }	 
	 
	public static void main(String[] args) throws IloException
	 {
	 	IloCplex cplex = new IloCplex();
	 	cplex.setParam(IloCplex.Param.TimeLimit, 600);//Runtime 600s
	 	cplex.setParam(IloCplex.Param.Threads, 1);//only use one thread currently
	 	cplex.setParam(IloCplex.Param.RootAlgorithm, 1);//choose algorithm
	 	
	 	OrignData orignData = new OrignData();
	 	double[][] node = new double[225][3];
//		node = readTxt("tsp225.opt.tour");
		node = orignData.data;
		//def xij
		IloNumVar [][] x=new IloIntVar[225][225];
		for(int i=0; i<225; i++)
		{
			for(int j=0; j<225; j++)
			{
				x[i][j]=cplex.boolVar("");//
			}
		}
		//def ui
		IloNumVar [] u=new IloIntVar[225];
		u[0]=cplex.numVar(0, 0, IloNumVarType.Int);
		u[1]=cplex.numVar(1, 1, IloNumVarType.Int);
		for(int j=2; j<225; j++)
		{
			u[j]=cplex.numVar(2, 225, IloNumVarType.Int);
		}
		//def objective
	 	IloNumExpr obj = cplex.numExpr();
		for(int i=0; i<225; i++)
		{
			for(int j=0; j<225; j++)
			{
				if(i!=j)
				{
					double distance_x = node[i][1]-node[j][1];
					double distance_y = node[i][2]-node[j][2];
					obj = cplex.sum(obj, cplex.prod(Math.sqrt(distance_x*distance_x + distance_y*distance_y), x[i][j]));
				}
			}
		}
	 	cplex.addMinimize(obj);
	 	
		//sigm xij=1
	 	for(int i = 0; i < 225; i++)
	 	{
	 		IloLinearNumExpr expr = cplex.linearNumExpr();
	 		for(int j = 0; j < 225; j++)
	 		{
	 			if(i!=j)
	 			{
	 				expr.addTerm(1, x[i][j]);
	 			}
	 			else
	 			{
	 				continue;
	 			}
	 		}
	 		cplex.addEq(expr, 1);	 		
	 	}
	 	//sigm xji=1
	 	for(int i = 0; i < 225; i++)
	 	{
	 		IloLinearNumExpr expr = cplex.linearNumExpr();
	 		for(int j = 0; j < 225; j++)
	 		{
	 			if(i!=j)
	 			{
	 				expr.addTerm(1, x[j][i]);
	 			}
	 			else
	 			{
	 				continue;
	 			}
	 		}
	 		cplex.addEq(expr, 1);	 		
	 	}
	 	//=
	 	for(int i = 0; i < 225; i++)
	 	{
	 		IloLinearNumExpr expr = cplex.linearNumExpr();
	 		for(int j = 0; j < 225; j++)
	 		{
	 			if(i!=j)
	 			{
	 				expr.addTerm(1, x[i][j]);
	 				expr.addTerm(-1, x[j][i]);
	 			}
	 			else
	 			{
	 				continue;
	 			}
	 		}
	 		cplex.addEq(expr, 0);	 		
	 	}	 	

	 	//ui>=1+ui+(xij-1)M
	 	for(int i = 1; i < 225; i++)
	 	{
	 		for(int j = 1; j < 225; j++)
	 		{
 				IloLinearNumExpr expr = cplex.linearNumExpr();
	 			expr.addTerm(1, u[i]);
	 			expr.addTerm(-1, u[j]);
	 			expr.addTerm(227, x[i][j]);
	 			cplex.addLe(expr, 226);
	 		}
	 	}
	 	
	 	//solve
	 	cplex.solve();
	 	System.out.println("status:"+cplex.getStatus());//get status
	 	System.out.println("bojective cost:"+cplex.getObjValue());//get objective value
	 	
	 }	
}
